Односторонняя функция с потайным входом
Односторонняя функция с потайным входом (англ. trapdoor function, TDF) — это односторонняя функция [math]\displaystyle{ f }[/math] из множества [math]\displaystyle{ X }[/math] в множество [math]\displaystyle{ Y }[/math], обладающая свойством (потайным входом, лазейкой), благодаря которому становится возможным найти для любого [math]\displaystyle{ y \in Im{f}, x \in X }[/math] такое, что [math]\displaystyle{ f(x) = y }[/math], то есть обратить функцию.
Односторонние функции с потайным входом широко используются в асимметричных методах шифрования (шифрование с открытым ключом) таких как: RSA, функция Рабина, схемы Эль-Гамаля, криптосистема McEliece, криптографическая система NTRUEncrypt, Polly Cracker, а также в менее популярной, из-за своей криптографической нестойкости, ранцевой криптосистеме Меркла — Хеллмана.
В настоящее время доподлинно не установлено, что односторонние функции с потайным входом действительно являются односторонними, то есть нет доказательства того, что, не зная потайной вход, криптоаналитик не сможет обратить функцию.
Определение
Функция [math]\displaystyle{ f:\{0,1\}^{l(n)} \times \{0,1\}^{n} \xrightarrow[]{} \{0,1\}^{m(n)} }[/math], где
[math]\displaystyle{ \{0,1\}^{l(n)} }[/math] — множество открытых ключей,
[math]\displaystyle{ \{0,1\}^{m(n)} }[/math] — отображаемый элемент, состоящий из n битов,
называется односторонней с потайным входом, если
- Она является односторонней;
- Существует эффективный алгоритм, который при заданных открытом ключе [math]\displaystyle{ Y }[/math], сообщении [math]\displaystyle{ M }[/math] и значении функции вычисляет [math]\displaystyle{ M' }[/math] такое, что [math]\displaystyle{ f(M) = f(M') }[/math] для некоторого ключа [math]\displaystyle{ Z }[/math];
- Для данного сообщения [math]\displaystyle{ M }[/math] и функции [math]\displaystyle{ f(M) }[/math] трудно найти сообщение [math]\displaystyle{ M' \neq M }[/math] такое, что [math]\displaystyle{ f(M) = f(M') }[/math].
История
Развитие односторонних функций с потайным входом
Понятие односторонней функции с потайным входом было введено в середине 1970-х годов после публикации Уитфилдом Диффи, Мартином Хеллманом и Ральфом Мёрклом статьи об асимметричных методах шифрования (шифрование с открытым ключом). Именно Диффи и Хеллман ввели данный термин[1]. Но первой системой, в которой были использованы такие идеи, считается система, изобретённая в 1973 году Клиффордом Коксом , работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года[2].
Статья описывала новый способ для минимизации необходимости передачи ключей по защищённым каналам, а также в ней была разобрана криптографическая система, которая может использоваться в создании цифровой подписи[3].
Авторы показали, что односторонняя функция с потайным входом может быть использована в криптосистемах с открытым ключом и в устройстве цифровой подписи[4]. Криптосистема с открытым ключом — система, в которой открытый ключ передается по незащищённому каналу. Смысл цифровой подписи заключается в том, что при пересылке подписанного сообщения от Алисы к Бобу, Боб может убедиться в том, что сообщение действительно было послано Алисой.
Благодаря односторонним функциям с потайным входом могут быть реализованы различные шифры с потайным входом, которые являются криптозащищёнными[1].
Было предложено несколько классов функций, но скоро стало понятно, что подходящие функции труднее найти, чем считалось изначально. Например, сначала предполагалось использовать функции, основанные на задаче о сумме подмножеств. Вскоре выяснилось, что этот способ неприемлем. Примером подобной реализации может служить ранцевая криптосистема Меркла — Хеллмана.
В 2005 году самыми подходящими кандидатами в односторонние функции с потайным входом являлись функции из классов RSA и Рабина [5]. Эти функции используют возведение в степень по модулю составного числа, и обе они основаны на задаче факторизации целых чисел.
В 2008 году были представлены односторонние функции с потайным входом, допускающие потерю информации о изначальном сообщении.
Развитие односторонних функций с потайным входом, допускающих потери
Данный тип функций (lossy trapdoor function), основывающийся на идее повреждения значительной части информации[6], был представлен Крисом Пейкертом и Брентом Уотерсом [7] в частности, как средство построения схемы шифрования с открытым ключом с выбранным-зашифрованным текстом.
Множество данных функций состоит из семейства двух функций:
- Повторяют работу односторонней функции с потайным входом без потери части информации, то есть при наличии «лазейки» можно эффективно вычислить [math]\displaystyle{ x }[/math] по значению [math]\displaystyle{ f(x) }[/math].
- Теряют часть информации о входе, тогда у выхода [math]\displaystyle{ f(x) }[/math] существует много прообразов (то есть невозможно однозначно обратить функцию).
Ключевым моментом является то, что выбранные семейства функций — полиномиально неразличимы . Следовательно, ключи могут быть заменены ключами с потерями без уведомления кого-либо. Но как только все ключи потеряны, шифрованный текст больше не содержит (значительную) информацию об зашифрованном сообщении. В то же время, если просто заменить функцию с лазейкой функцией с потерями, то нет возможности ответить даже на правильно сформированный запрос на дешифрование, потому что информация открытого текста будет утеряна. Поэтому используются более полные абстракции
Односторонние функции с потайным входом «All-but-one»
Функция «All-but-one» (ABO) может быть построена из набора односторонних функций с потайным входом и с достаточной потерей информации.
Набор функций ABO связан с множеством [math]\displaystyle{ B }[/math], элементы которого называются ветвями. Генератор функции ABO принимает дополнительный параметр [math]\displaystyle{ b^* \in B }[/math], называемый ветвью с потерями, и выводит функцию [math]\displaystyle{ g({\cdot}, {\cdot}) }[/math] и потайной ход t. Функция [math]\displaystyle{ g }[/math] обладает тем свойством, что для любой ветви [math]\displaystyle{ b \not= b^* }[/math] функция [math]\displaystyle{ g (b, \cdot) }[/math] обладает потайным входом (и может быть инвертирована с [math]\displaystyle{ t }[/math]), но функция [math]\displaystyle{ g (b^*, \cdot) }[/math] — функция с потерями. Более того, ветвь с потерями скрыта (вычислительно) по описанию [math]\displaystyle{ g }[/math].[8].
Односторонние функции с потайным входом «All-but-N»
«All-but-N»(ABN) функции имеют ровно [math]\displaystyle{ N }[/math] веток с потерями; все другие ветки обладают потайным входом. Это можно использовать для точного определения зашифрованных текстов с помощью веток с потерями — все другие зашифрованные тексты соответствуют функциям с лазейкой и могут быть дешифрованы. Обратите внимание, что ABN кодируют набор веток с потерями по их ключу. То есть вычислительно неограниченный противник всегда может использовать грубую силу, для поиска ветвей, приводящих к функции с потерями.
Следовательно, ABN функции имеют серьезный недостаток: а именно, пространственная сложность ключей линейна в [math]\displaystyle{ N. }[/math][9]
Односторонние функции с потайным входом «All-but-many»
«All-but-many»(ABM) функция имеет суперполиномиальное множество ветвей с потерями, которые требуют наличия специального потайного хода.
Самое важное отличие от ABN-функции: с ABN набор ветвей с потерями указывается первоначально, во время построения, а ABM функции имеют лазейку, позволяющую пробовать дешифровку «на лету» из большого пула ветвей с потерями. Без этого потайного хода и даже при произвольном известном множестве ветвей с потерями нет возможности найти другую ветвь, не принадлежащую известному множеству. Это, в частности, позволяет создавать экземпляры ABM с компактными ключами и изображениями, размер которых не зависит от количества ветвей с потерями.
Данные конструкции можно рассматривать как «замаскированные» варианты сигнальных схем Boneh-Boyen (BB). В частности, ветви с потерями соответствуют действительным сигнатурам. Тем не менее, чтобы метки потерь и метки потайных ходов казались неотличимыми, необходимо делать слепые подписи, путем их шифрования или путем умножения на случайный элемент подгруппы.[9]
Построение односторонних функций с потайным входом с потерями
Чтобы отметить основные принципы, предположим, что общая криптосистема с поддержкой CPA имеет несколько специальных (но неформально описанных) свойств.
Первое свойство предполагает, что лежащая в основе криптосистема аддитивно-гомоморфна. Функция [math]\displaystyle{ f }[/math] (односторонняя функция с лазейкой или функция с потерями) на [math]\displaystyle{ \{0, 1\}^n }[/math] определяется путем шифрования поэлементно квадратной матрицы [math]\displaystyle{ M }[/math].
Для оценки [math]\displaystyle{ f(x) }[/math], подаем вход [math]\displaystyle{ x \in \{0, 1\}^n }[/math] — n-мерный бинарный вектор и вычислим (поэтапно) шифрование линейного произведения [math]\displaystyle{ x*M }[/math], применяя гомоморфные операции к зашифрованным записям [math]\displaystyle{ M }[/math].
Для функции с потайным входом зашифрованная матрица [math]\displaystyle{ M }[/math] является единичной матрицей [math]\displaystyle{ I }[/math], а лазейка является ключом дешифрования для криптосистемы. Функция [math]\displaystyle{ f }[/math] обратима с помощью потайного входа, потому что [math]\displaystyle{ f(x) }[/math] — это входное шифрование [math]\displaystyle{ x * I = x }[/math], которое может быть дешифровано до значения каждого бита [math]\displaystyle{ x }[/math].
Для функции с потерями зашифрованная матрица [math]\displaystyle{ M }[/math] является матрицей, состоящей из нулей: [math]\displaystyle{ M = 0 }[/math]. Тогда, для каждого входного сообщения [math]\displaystyle{ x }[/math], значение [math]\displaystyle{ f(x) }[/math] является поэлементным шифрованием нулевого-вектора, поэтому [math]\displaystyle{ f }[/math] "теряет" информацию о [math]\displaystyle{ x }[/math] . Однако этого недостаточно для обеспечения полной потери, поскольку выходные зашифрованные сообщения по-прежнему несут некоторую внутреннюю случайную информацию, которая может служить источником данных о входном сообщении. Поэтому необходим дополнительный контроль за их поведением. Для этого существуют специальные свойства криптосистемы:
- случайности можно использовать повторно в комбинациях с различными ключами без ухудшения стойкости.
- гомоморфная операция изолирует случайность, то есть случайность выходного шифротекста зависит только от случайностей во входном сообщении (а не от открытого ключа или зашифрованных сообщений). Многие известные криптосистемы гомоморфны по отношению к случайности.
С этими двумя свойствами зашифровываем матрицу [math]\displaystyle{ M }[/math] особым образом. Каждый столбец [math]\displaystyle{ j }[/math] матрицы связан с другим ключом [math]\displaystyle{ p_{kj} }[/math], а лазейка — это набор соответствующих ключей расшифровки. Через каждую строку [math]\displaystyle{ i }[/math] шифруем запись [math]\displaystyle{ m_{i,j} }[/math] под ключ [math]\displaystyle{ p_{kj} }[/math] и ту же случайность [math]\displaystyle{ r_i }[/math] (используя новую случайность для каждой строки). По условию, повторно использовать случайность в паре с ключом [math]\displaystyle{ p_{kj} }[/math] безопасно, поэтому матрица [math]\displaystyle{ M }[/math] является вычислительно скрытой. Кроме того, поскольку гомоморфизм изолирует случайность, все зашифрованные тексты в конечном векторе [math]\displaystyle{ f(x) }[/math] также зашифровываются под такую же случайность [math]\displaystyle{ R }[/math] (которая зависит только от [math]\displaystyle{ (r_1, r_2 ... r_m) }[/math].
Когда [math]\displaystyle{ M = I }[/math], мы все ещё можем инвертировать функцию (с помощью лазейки), расшифровывая каждую зашифрованную запись [math]\displaystyle{ f(x) }[/math]. С другой стороны, когда матрица нулевая [math]\displaystyle{ M = 0 }[/math], выход функции всегда является вектором зашифрованных нулевых сообщений, где каждая запись зашифровывается по одной и той же случайности (но под разными фиксированными ключами). Поэтому число возможных выходов [math]\displaystyle{ f }[/math] ограничено числом возможных случайных строк, которые могут возникнуть. Выбирая размерность [math]\displaystyle{ n }[/math] так, что количество входов [math]\displaystyle{ 2^n }[/math] является значительно больше, чем число случайных строк, мы можем гарантировать, что функция содержит потею информации.
Построение функций с потайным ходом «All-but-one»
Построение функций «All-but-one» с потайным входом несколько более общее. Каждая ветвь [math]\displaystyle{ b }[/math] функции просто соответствует другой матрице [math]\displaystyle{ M_b }[/math], шифрование которой может быть получено из публичного описания функции. Функция генерируется так, что [math]\displaystyle{ M_b }[/math] является обратимой матрицей (и вычисляется с помощью потайного входа) для всех ветвей [math]\displaystyle{ b }[/math], тогда как [math]\displaystyle{ M_{b^*} = 0 }[/math] для ветвей с потерями [math]\displaystyle{ b^* }[/math]
Примеры односторонних функций с потайным входом
RSA
Возьмём число [math]\displaystyle{ n = p \cdot q }[/math], где [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] принадлежат множеству простых чисел. Считается, что для данного числа [math]\displaystyle{ n }[/math] вычисление [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] является математически трудной задачей. Функция шифрования RSA — [math]\displaystyle{ E(m) = m^e \mod n }[/math], где [math]\displaystyle{ e }[/math] — взаимнопростое с [math]\displaystyle{ (p-1)(q-1) }[/math]. Числа [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] являются потайным входом, зная которые вычислить обратную функцию [math]\displaystyle{ E^{-1} }[/math] легко. На сегодняшний день лучшей атакой на RSA является факторизация числа [math]\displaystyle{ n }[/math][10][11].
Функция Рабина
Рассмотрим функцию [math]\displaystyle{ F(x, n) = x^2 mod(n) }[/math], где [math]\displaystyle{ n = p \cdot q }[/math], а p и q принадлежат множеству простых чисел. Рабин показал, что вычислить функцию [math]\displaystyle{ f^{-1} }[/math] легко тогда и только тогда, когда разложение на множители составного числа из двух простых является простой задачей[12].
Схема Эль-Гамаля
Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Она основывается на задаче дискретного логарифмированияШаблон:Source-ref.
Алгоритм
- Алиса выбирает простое число p и произвольное число a.
- Алиса вычисляет свой открытый ключ (а, b), где [math]\displaystyle{ b=a^{c} }[/math], [math]\displaystyle{ 1\lt c\lt p }[/math]
- Боб выбирает [math]\displaystyle{ 1\lt d\lt p }[/math] и шифрует сообщение m: [math]\displaystyle{ (m_1,m_2) = (a^d, m \cdot b^d) }[/math]
- Алиса расшифровывает сообщение [math]\displaystyle{ m = m_2 \cdot (m_1^{c})^{-1}. }[/math]
Криптосистема Polly Cracker
Алгоритм[13]
- Алиса случайным образом выбирает вектор в конечном поле.
- Алиса строит полиномы, которые в точке, задаваемой этим вектором, обращаются в ноль.
- Боб генерирует сумму [math]\displaystyle{ p=\sum {q_i \cdot b_i} }[/math]
- Боб посылает [math]\displaystyle{ p+m }[/math]
Другие примеры
Известно, что функции, связанные с задачей дискретного логарифмирования, не являются односторонними функциями с потайным входом, потому что нет никакой информации о «лазейке», которая позволила бы эффективно вычислять дискретный логарифм. Однако, задача дискретного логарифмирования может использоваться в качестве основы для «лазейки», например, вычислительная задача Диффи-Хеллмана (CDH) и его разновидности. Алгоритм цифровой подписи основан на данной вычислительной задаче.
Замечания
Односторонние функции с потайным входом имеют очень специфическое применение в криптографии и их не нужно путать с бэкдором (часто одно понятие подменяется другим, но это неправильно). Бэкдор — механизм, который намеренно добавляется к шифровальному алгоритму (например, алгоритм генерации ключевых пар, алгоритм цифровой подписи, и т. д.) или к операционным системам, позволяя одному или нескольким посторонним лицам обходить или подрывать безопасность системы.
См. также
Примечания
- ↑ 1,0 1,1 Diffie, Hellman, 1976, p. 652.
- ↑ Cliff Cocks. Cliff Cocks papper (недоступная ссылка). Дата обращения: 23 ноября 2017. Архивировано 16 февраля 2017 года.
- ↑ Diffie, Hellman, 1976, p. 644.
- ↑ Diffie, Hellman, 1976, pp. 647—649.
- ↑ Katja Schmidt-Samoa. A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications (англ.) // Electronic notes in theoretical computer science. — Elsevier, 2006. — Vol. 157. — P. 79—94. — ISSN 1571-0661. — doi:10.1016/j.entcs.2005.09.039.
- ↑ Peikert, Waters, 2008, pp. 8.
- ↑ Peikert, Waters, 2008, pp. 6.
- ↑ Peikert, Waters, 2008, pp. 13—14.
- ↑ 9,0 9,1 Chris Peikert, Brent Waters. Lossy Trapdoor Functions and Their Applications∗ (англ.) // Proceeding STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing. — 2008. — Vol. 41. — P. 79—94. — ISSN 1571-0661. — doi:10.1145/1374376.1374406.
- ↑ Daniel Lerch Hostalot. Factorization Attack to RSA (англ.) // Hakin9 : journal. — 2007.
- ↑ S. Goldwasser, M. Bellaret. Lecture Notes on Cryptography (англ.) : journal. — 2008.
- ↑ Katja Schmidt-Samoa. A New Rabin-type Trapdoor Permutation Equivalent to Factoring and Its Applications (англ.) : journal. — 2005.
- ↑ Neal Koblitz, 1998, pp. 105—106.
Литература
- Xavier Boyen, Xiaofeng Chen. General Construction of Chameleon All-But-One Trapdoor Functions // Provable Security: 5th International Conference (англ.). — Springer, 2011. — P. 257—261. — ISBN 9783642243158.
- Giuseppe Longo. Section 4.2: Cryptographic functions // Secure digital communications (неопр.). — 1983. — С. 29—30. — ISBN 0-387-81784-0.
- Chris Peikert, Brent Waters. Lossy Trapdoor Functions and Their Applications (англ.). — 2008. — ISBN 978-1-60558-047-0.
- Julien Cathalo, Christophe Petit. One-time trapdoor one-way functions (англ.). — Springer, 2011. — ISBN 9783642181771.
- Ronald C. Mullin, Gary L. Mullen. Finite fields : theory, applications, and algorithms : Fourth International Conference on Finite Fields: Theory, Applications, and Algorithms (англ.). — Providence, R.I. : American Mathematical Society, 1998. — ISBN 0821808176.
- Neal Koblitz. Algebraic aspects of cryptography. — Springer. — 1998. — ISBN 3540634460.
- Шаблон:Source